package algorithm.binaryTreeAlgorithm;

import data.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName: Tree2Str
 * @Description 606. 根据二叉树创建字符串
 * 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
 *
 * 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
 *
 * @Author skywingking
 * @Date 2022/3/19 6:23 下午
 **/
public class Tree2Str {
    public String tree2str(TreeNode root){
        StringBuffer ans = new StringBuffer();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        stack.push(root);
        Set<TreeNode> visited = new HashSet<>();
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(!visited.add(node)){
                if (node != root) {
                    ans.append(")");
                }
                stack.pop();
            }else{
                if (node != root) {
                    ans.append("(");
                }
                ans.append(node.val);
                if (node.left == null && node.right != null) {
                    ans.append("()");
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
        return ans.toString();
    }
}